﻿//132. 分割回文串 II
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
//返回符合要求的 最少分割次数 。

class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool>> arr(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                bool isPalindrome = true;
                for (int left = i, right = j; left < right; left++, right--)
                {
                    if (s[left] != s[right])
                    {
                        isPalindrome = false;
                        break;
                    }
                }
                arr[i][j] = isPalindrome;
            }
        }

        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < n; i++)
        {
            if (arr[0][i])
            {
                dp[i] = 0;
            }
            else
            {
                for (int j = 0; j < i; j++)
                {
                    if (arr[j + 1][i])
                    {
                        dp[i] = min(dp[j] + 1, dp[i]);
                    }
                }
            }
        }
        return dp[n - 1];
    }
};